package com.duoduo.algs4.DataStructure;

import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;

public class Stack<Item> implements Iterable<Item> {
	private int N;
	private Node first;

	public Stack() {
		first = null;
		N = 0;
		assert check();
	}

	private class Node {
		private Item item;
		private Node next;
	}

	public void push(Item item) {
		Node node = new Node();
		node.item = item;
		node.next = first;
		first = node;
		N++;
		assert check();
	}

	public Item pop() {
		if (N == 0) {
			throw new NoSuchElementException("栈为空");
		}
		Item item = first.item;
		first = first.next;
		N--;
		assert check();
		return item;

	}

	public boolean check() {
		if (N == 0) {
			if (first != null) {
				return false;
			}
		} else if (N == 1) {
			if (first == null) {
				return false;
			}
			if (first.next != null) {
				return false;
			}
		} else {
			if (first.next == null) {
				return false;
			}
		}
		// check internal consistency of instance variable N
		int numberOfNodes = 0;
		for (Node x = first; x != null; x = x.next) {
			numberOfNodes++;
		}
		if (numberOfNodes != N) {
			return false;
		}
		return true;
	}

	public int size() {
		return N;
	}

	public boolean isEmpty() {
		return N == 0;
	}

	public Item peep() {
		if (first == null) {
			throw new NoSuchElementException("栈为空");
		}
		return first.item;
	}

	public Iterator<Item> iterator() {
		return new ListIterator();
	}

	private class ListIterator implements Iterator<Item> {
		private Node current = first;

		public boolean hasNext() {
			return current == null;
		}

		public Item next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			Item item = current.item;
			current = current.next;
			return item;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	public static void main(String[] args) {
		Stack<String> stack = new Stack<String>();
		while (!StdIn.isEmpty()) {
			stack.push(StdIn.readString());
		}
		while (!stack.isEmpty()) {
			StdOut.print(stack.pop() + " - ");
		}

	}

}
